package leetcode_二叉树;

/**
 * 填充每个节点的下一个右侧节点指针 II
 * 算法: 层序遍历
 *
 * @author yezh
 * @date 2023/11/3 10:53
 */
public class _117 {

    public Node connect(Node root) {
        if (root == null) return root;
        Node cur = root, pre, dummy;
        while (cur != null) {
            dummy = new Node();
            pre = dummy;
            // while 结束后, 下一层节点就连起来了
            while (cur != null) {
                if (cur.left != null) {
                    pre.next = cur.left;
                    pre = cur.left;
                }
                if (cur.right != null) {
                    pre.next = cur.right;
                    pre = cur.right;
                }
                cur = cur.next;
            }
            // dummy.next 指向了下一层的第一个节点
            cur = dummy.next;
        }
        return root;
    }

    static class Node {
        int val;
        Node left;
        Node right;
        Node next;
    }

}
